1. Technical Field
The present inventions relates to halftone patterns generally used for printing and image display, and in particular, to stochastic halftone patterns.
2. Description of the Related Art
Most printers (and some displays) are binaryxe2x80x94they can either print a fixed-size dot on the paper or not at each point in a discrete array. There is no inherent gray scale capability. See R. Rylander, xe2x80x9cElectronic Halftonesxe2x80x9d, presented at the xe2x80x9cLasers in Graphicsxe2x80x9d conference, ca. 1990, which is incorporated herein by reference.
Virtually all images, on the other hand, contain a continuum of shades from black to white (or a full range of colors). To simulate these varying shades (or colors), binary printers and displays either adjust the size of dots, or adjust the spacing between the dots. Halftone screens are used to determine how large to make the dots or how far apart to space them to represent a particular image.
Most conventional halftone screens use fixed spot positions at a well defined pitch (frequency), and vary the size of the spot to change shade. The high level of periodicity in conventional halftone screens can produce significant moire or interference effects when an image having strong periodic structures is halftoned, or screens are superimposed for multi-color printing.
Stochastic screens greatly reduce, or even eliminate, this periodicity. Removing the periodicity from the halftone texture in turn greatly reduces the appearance of moirxc3xa9 or interference effects. Moirxc3xa9 effects can also be reduced or eliminated when multiple stochastic halftone screens are combined for color printing.
The term xe2x80x9cstochastic screeningxe2x80x9d can be applied to any halftone process that is aperiodic in nature, producing random or pseudo-random, irregular textures. Most stochastic screens can also be categorized as xe2x80x9cdispersed dotxe2x80x9d screens, representing different shades by varying the number of isolated, same-size spots per unit area, rather than using different size spots at fixed locations, as with conventional halftone screens.
A widely used form of stochastic screening is the xe2x80x9cerror diffusionxe2x80x9d process introduced by Floyd and Steinberg, (R. Floyd and L. Steinberg, xe2x80x9cAn Adaptive Algorithm for Spatial Grey Scalexe2x80x9d, SID Digest, pp. 36-37 (1975)), and the various modifications that have since appeared in the literature. The original error diffusion algorithm was not in itself xe2x80x9cstochasticxe2x80x9d, but completely deterministic. The dot pattern of a halftone raster image was determined by comparing the value of each continuous tone pixel of the input image added to an accumulated error term with a threshold value to make an xe2x80x9call-or-nothingxe2x80x9d decision (print a spot at that raster point or not). The difference between the desired shade and the minimum (paper) or maximum (ink) shade actually used is then added to the error term. While the image was generally processed in a strict raster fashion, the errors were not simply pushed into the next raster-order pixel, but given a two-dimensional distribution in a way that produces subjectively pleasing textures for most shades.
Error diffusion produces a dot sequence with shade-dependent duty factor. While some shades correspond to simple duty factors (i.e., a medium gray would be printed as a simple on-off-on checkerboard pattern), most do not, resulting in textures that exhibit locally coherent patterns disturbed by semi-regular phase jumps in the attempt to reconcile some fractional duty cycle with the integer addressability of the raster device. These phase jumps (which look similar to crystal dislocations) make noise-free synthetic (computer-generated) images processed with conventional error diffusion generally unpleasant.
The inevitable low level noise in xe2x80x9cnaturalxe2x80x9d (scanned) images adds a randomizing element that suppresses the formation of significant coherent pattern areas. The benefits of intentionally adding low level noise have been recognized in several modifications of the error diffusion technique, making it truly xe2x80x9cstochasticxe2x80x9d. (See R. J. Rolleston and S. J. Cohen, xe2x80x9cHalftoning with Random Correlated Noisexe2x80x9d, J. Electron. Imag., 1(2) pp. 209-217 (April 1992); K. T. Knox and R. Eschback, xe2x80x9cThreshold Modulation in Error Diffusionxe2x80x9d, J. Electron. Imag., 2(3) pp. 185-192 (July 1993)). Other attempts to improve the appearance involve changing the weights or the size of the neighborhood for error distribution, or modification of the raster path through the image (serpentine, peano curve, etc.) (see R. Stevens, A. Lehar and F. Preston, xe2x80x9cManipulation and Presentation of Multidimensional Image Data Using the Peano Scanxe2x80x9d, IEEE Trans. on Pattern Analysis and Machine Intelligence PAMI-5, No. 5, pp. 520-526 (1983)).
Error diffusion processes have the advantage of being dynamic, capable of adjusting their bit-rate on the fly for an optimal pattern at any shade level. The same dynamic behavior is also a disadvantage, however, in that the processes are causalxe2x80x94they only xe2x80x9cknowxe2x80x9d past pixels. This leads to various hysteresis and edge-related artifacts. In addition, the improvements to the original, fully determinative, technique require additional calculations per point, compromising the performance of what is in its basic form already a relatively slow process.
Very fast halftone processing that produces images with textures similar to error diffusion results can be achieved through the use of a xe2x80x9cBlue Noise Maskxe2x80x9d (T. Mitsa and K. J. Parker, xe2x80x9cDigital Halftoning Technique Using a Blue-Noise Maskxe2x80x9d, J. Opt. Soc. Am. A 9, pp. 1920-1929 (1992); M. Yao and K. J. Parker, xe2x80x9cModified Approach to the Construction of a Blue Noise Maskxe2x80x9d, J. Electron. Imag. 3(1) pp. 92-97 (Jan. 1994); U.S. Pat. No. 5,111,310 (Parker et al.); U.S. Pat. No. 5,341,228 (Parker et al.); U.S. Pat. No.5,477,305 (Parker et al.); U.S. Pat. No. 5,543,941 (Parker et al.)). With this technique, a matrix of threshold values is computed to exhibit a so-called blue-noise spectrum in the Fourier domain. The value of each pixel in an image is then compared to the threshold value in the corresponding cell of the matrix. If it is above the threshold value, it is considered a 1 (solid ink or image dot), and if it is below the threshold value, it is considered a 0 (blank paper or screen). Pixels values matching the threshold value can be considered a 1 or a 0 at the designer""s choice, or shifted one way or the other on a random or pseudo-random basis.
With a blue noise mask, the calculation per pixel is just a simple comparison of shade values with corresponding mask values, so printing or displaying an image is quite fast. However, such pre-computed threshold matrices (masks) may not necessarily produce optimal (i.e., xe2x80x9cshade-adaptivexe2x80x9d) textures. The spot distributions must be monotonic (constrained by previous shade textures), but they are anticipatory or non-causal and can produce more spatially isotropic and homogeneous textures that are insensitive to image structures. In addition, generating the blue noise mask with appropriate statistical and visual characteristics as described by Parker et al. is quite complicated, requiring iterative manipulations in the Fourier (spatial frequency) domain for each shade value.
More important, the blue-noise spectrum masks are heavily biased toward high frequencies. The emphasis of high spatial frequencies in dispersed dot patterns is an advantage in minimizing the visibility of halftone textures particularly on low addressability printers (such as ink jet or electrostatic) as long as the printer has sufficient resolution to properly render individual spots. The number of resolvable spots in a unit area is limited by the addressability and by the minimum spot size which an imaging engine, such as a printer or display screen, is capable of making. When the frequencies of the halftone exceed the capability of the engine, the spots blur together, a form of dot gain. The resulting image then in fact emphasizes low frequencies, which is usually highly undesirable as it generates visually obtrusive patterns in the image.
Dalton has suggested the use of a xe2x80x9cbandpassxe2x80x9d stochastic mask, that is, a mask with a maximum frequency to minimize sensitivity to printer dot gain. J. Dalton, xe2x80x9cPerception of Binary Texture and the Generation of Stochastic Halftone Screensxe2x80x9d, SPIE Proc. Human Vision, Visual Processing and Digital Display VI, pp. 207-220 (1995). However, he provided no information as to how such a screen might be generated or optimized for various printer or display characteristics.
All of the foregoing mask techniques also have problems because they assume perfect registrations between different color separations. In the real world, printers are not perfect, and dots of different colors may have slightly different diameters or slightly different positions from those planned. This can create visually discordant images, which are particularly problematic at high frequencies.
A new type of stochastic (pseudo-random) halftone pattern has been invented which has a narrow band power spectrum. Preferably when used for multiple color separations, the spectrum also is made anisotropic (angularly dependent). The narrow band property helps control dot gain (resulting in smoother textures), and the anisotropy may be used to de-couple sets of patterns for color printing with reduced color noise or mottle.
According to the present invention, a new approach is used to generate a halftone threshold matrix. The generation process is a means of ranking (assigning threshold values to) the elements of the threshold array to determine which dots will be printed in a corresponding halftone image to simulate a given shade of gray. Since the dot pattern is to be stochastic, or pseudo-random, in appearance, the threshold matrix is generally very large, e.g., a two-dimensional array of 256xc3x97256 elements. In addition to the threshold matrix itself, an auxiliary matrix of the same size is defined that will be used to store an xe2x80x9caccumulated biasxe2x80x9d measure.
An arbitrary element of the threshold matrix is assigned the lowest rank threshold value (the rank will range from 0 to 65535 for the 256xc3x97256 element matrix used to illustrate this description). The elements of the auxiliary xe2x80x9caccumulated biasxe2x80x9d matrix are then assigned bias values calculated by a formula based on the distance of each element from the corresponding ranked threshold matrix element. The bias value formula has a behavior which is xe2x80x9crepulsivexe2x80x9d for large element distances, and xe2x80x9cattractivexe2x80x9d for short distances.
The element of the threshold matrix which will be assigned the next sequential rank is determined by searching the corresponding xe2x80x9caccumulated biasxe2x80x9d matrix for the element with lowest bias. As each threshold matrix element is ranked, the bias values based on distances to the new element are added to the previous values in the xe2x80x9caccumulated biasxe2x80x9d matrix. The large-distance repulsive behavior of the bias formula ensures that initially, the ranked elements of the threshold matrix will be as mutually far apart as possible.
As the ranking process progresses, the mean distance between ranked elements of the threshold matrix decreases. At some point, this mean distance falls to a level where the short-range xe2x80x9cattractivexe2x80x9d behavior of the bias function takes over and accumulated bias minima will be found adjacent to previously ranked element locations rather than between them. That is, existing dispersed dots will begin to grow.       f    ⁡          (      d      )        =            a      +              b        ⁢                  xe2x80x83                ⁢                  d          2                            a      +              d        4            
with a and b representing constants selected to optimize the threshold matrix for the particular imaging engine (printer or display) with which the matrix will be used, and where d represents the distance from the element for which the bias is being calculated.
The ranking process continues until all elements of the halftone threshold matrix have been assigned a value. Since the range of rank values will generally greatly exceed the number of shades to be approximated (digital images typically are quantized to 256 discrete shade levels), a mapping process is applied to scale the threshold matrix values to the desired shade range. This mapping process will result in multiple elements of the threshold matrix having the same valuexe2x80x94at each shade step more than a single dot will be added to the halftone pattern. The mapping process can be nonlinear to correct for dot gain or other non-ideal behavior of the printer.
In most circumstances, an image will have more than 256xc3x97256 pixels, so this grid would be replicated to create a large enough matrix to cover the entire image. Since this is expected, normally it should be assumed that the grid is replicated, and the elements in at least part of the first ring of replicas should be included when making the accumulated bias calculation. This is particularly significant since failure to do this will result in edge effects, with the cells along each of the matrix inherently having a lower bias without the replicas then they would with the replicas.
The foregoing creates a deterministic matrix, which sometimes creates artifacts in the image display. Preferably, the matrix is made truly stochastic, by jittering the placement of at least the first portion of the elements. If the formula indicates that a particular element has the lowest bias, instead of ranking that element, an adjacent element is ranked, thereby introduce a slight jitter. It usually is not necessary to jitter all elements in a matrixxe2x80x94the randomness introduced by jittering the first three to ten percent will affect all remaining element selections, so that usually is sufficient.
Any formula meeting the characteristics described above (a xe2x80x9crepulsivexe2x80x9d component acting over longer distances and an xe2x80x9cattractivexe2x80x9d component acting over shorter distances) will have some characteristic transition spatial frequency where the behavior changes. This frequency can be tuned by modifying the formula, e.g., by changing the values of the constants a and b in the preferred formula. At the same time, any particular imaging engine (printer or display) has a maximum frequency it is actually capable of reproducing, which is the passband frequency of the engine. Preferably, the frequency in the formula is tuned so that it is just within the passband frequency of the imaging engine. This will maximize the resolution of the image, while minimizing dot gain.
The threshold matrices resulting from this technique will produce halftone patterns with characteristics that correspond to a circular ring in the Fourier domain and a power spectrum which is low at low frequencies, peaks at the mid-range characteristic frequency previously described, and low to moderate at the higher frequencies.
All of the above is for a single grayscale matrix. Color printers usually operate by having multiple color separations, with the grayscale matrix applied separately to each color separation, e.g., Cyan, Magenta, Yellow, Black. If identical matrices are used, any inaccuracies in the registration of printing or displaying the different colors will be quite obvious. The present invention therefore further provides means to minimize these effects by using a different matrix for each color.
The matrix can be made different by using a different arbitrary starting cell, or preferably, by changing the circular bias to an elliptical bias. This can be done by changing how the formula calculates the distance to the other elements. Instead of the true linear distance d, a coordinate transformation is applied to the values in the x and y directions (e.g., so that the x component of the distance contributes more than the y component). One preferred embodiment uses a scaling factor of s*x for the x dimension, and y/s for the y direction. The distance d used in the formula then is the square root of the sum of the squares of these two elements.
The result then is a pattern having an elliptical, rather than a circular, ring in the Fourier domain, i.e., it is anisotropic. By using a variety of scaling factors or changing the coordinate system, the major axis of the ellipse for each separation can be at a different angle.
The overlap of such directionally biased (anisotropic) arrays does not vary as much with mis-registration of the different separations it does with isotropic arrays. The result is that mis-registration becomes much less noticeable, and the resulting image is more pleasing to the eye.
The threshold matrices generated by this process then preferably are included in the usual printer drivers, and used with an image the manner of any threshold matrix. That is, the value of each pixel of an image is compared to the threshold value in the corresponding element in the mask, converted to a 1 if it is above the threshold, 0 if below, and arbitrarily to 1 or 0 if it equals the threshold.